Kadane's Algorithm

Kadane's algorithm is a dynamic programming algorithm used to find the maximum sum of a contiguous subarray within a one-dimensional array of numbers. It's an efficient solution with a time complexity of O(n).

How it works: The algorithm iterates through the array, keeping track of two values at each step:

1. current_max: The maximum sum ending at the current position.
2. global_max: The overall maximum sum found so far.

At each element, current_max is updated to be either the current element itself or the current element added to the previous current_max. If current_max becomes negative, it's reset to 0 (or the current element, depending on the variant, to handle all negative numbers). global_max is updated whenever current_max exceeds it.

def kadanes_algorithm(arr):
    """
    Finds the maximum sum of a contiguous subarray using Kadane's algorithm,
    and returns both the maximum sum and the subarray itself.

    Args:
        arr: A list of integers.

    Returns:
        A tuple containing:
            - The maximum sum of a contiguous subarray.
            - The contiguous subarray that yields the maximum sum.
    """
    if not arr:
        return 0, []

    max_so_far = arr[0]
    current_max = arr[0]
    start_index = 0
    end_index = 0
    current_start_index = 0

    for i in range(1, len(arr)):
        if arr[i] > current_max + arr[i]:
            current_max = arr[i]
            current_start_index = i
        else:
            current_max = current_max + arr[i]

        if current_max > max_so_far:
            max_so_far = current_max
            start_index = current_start_index
            end_index = i

    return max_so_far, arr[start_index : end_index + 1]

# Test cases
array1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum, subarray = kadanes_algorithm(array1)
print(f"Maximum sum for {array1}: {max_sum}, subarray: {subarray}") # Expected: 6 (from [4, -1, 2, 1])

array2 = [1]
max_sum, subarray = kadanes_algorithm(array2)
print(f"Maximum sum for {array2}: {max_sum}, subarray: {subarray}") # Expected: 1 (from [1])

array3 = [5, 4, -1, 7, 8]
max_sum, subarray = kadanes_algorithm(array3)
print(f"Maximum sum for {array3}: {max_sum}, subarray: {subarray}") # Expected: 23 (from [5, 4, -1, 7, 8])

array4 = [-1, -2, -3, -4]
max_sum, subarray = kadanes_algorithm(array4)
print(f"Maximum sum for {array4}: {max_sum}, subarray: {subarray}") # Expected: -1 (from [-1])

array5 = []
max_sum, subarray = kadanes_algorithm(array5)
print(f"Maximum sum for {array5}: {max_sum}, subarray: {subarray}") # Expected: 0 (from [])

Maximum sum for [-2, 1, -3, 4, -1, 2, 1, -5, 4]: 6, subarray: [4, -1, 2, 1]
Maximum sum for [1]: 1, subarray: [1]
Maximum sum for [5, 4, -1, 7, 8]: 23, subarray: [5, 4, -1, 7, 8]
Maximum sum for [-1, -2, -3, -4]: -1, subarray: [-1]
Maximum sum for []: 0, subarray: []

---